package G.二叉搜索树;

public class _450_删除二叉搜索树中的节点 {

    /**
     * 自解：root的数值和key对比 如果root数值小 root指针右移 判断字符为1
     * prev用来记root 的上一个节点
     * 如果在右子数上（from==1）
     *  如果到相等
     * @param root
     * @param key
     * @return
     */
  //  boolean isRoot = true;
    TreeNode prev = null;
    int from =0;
    public TreeNode deleteNode(TreeNode root, int key) {

        if (root.val== key){
            //表示根节点就是要找的那个
            if (prev == null){
                //1 找右子树最左边 的节点
            }else {

            }

        }

        if (root.val < key){//右移
            prev = root;
            root = root.right;
            from =1;

            deleteNode(root,key);
        }
        if (root.val > key){//左移
            prev = root;
            root = root.left;


            deleteNode(root,key);
        }
        return root;

    }

    /**
     * 分情况：
     * 叶子节点--节点直接置空就行
     * 有右边--用后驱（右子树中最小的那个）
     * 只有左边--用前驱（左子树中最大的那个）
     * 除了叶子以外的情况 节点是不删除的 只是更换数值 然后递归删除从下面放上来的那个直到换到叶子节点
     * @param root
     * @param key
     * @return
     */

    //求后继节点数值
    public int successor(TreeNode root){

        root = root.right;
        while (root.left != null){
            root = root.left;
        }
        return root.val;

    }

    //求前驱节点数值
    public int presuccessor(TreeNode root){
        root = root.left;
        while (root.right != null){
            root = root.right;
        }
        return root.val;
    }
    public TreeNode deleteNode1(TreeNode root, int key) {
        if (root == null){
            return null;
        }

        if (root.val > key){
            //1-递归左子树
            root.left = deleteNode(root.left,key);
        }else if (root.val <key){
            //2-递归右子树
            root.right = deleteNode(root.right,key);
        }else {

            //3-数值相等
            if (root.right == null && root.left == null){
                //a==叶子结点
                root = null;
            }else if (root.right != null){
                //b==有右子树
                root.val = successor(root);//后继赋值
                root.right = deleteNode(root.right,root.val);//递归删除右子树转上来的那个

            }else {
                //c==只有左子树
                root.val = presuccessor(root);//前驱赋值
                root.left = deleteNode(root.left,root.val);//递归删除右子树转上来的那个
            }
        }


        return root;
    }


}
